Sequential decoding of convolutionally encoded data is a well known error correction scheme which has been used very successfully on channels with random noise. In U.S. Pat. No. 3,457,562 to Robert M. Fano, there is disclosed an error correcting sequential decoder wherein a sequential decoding receiver contains an encoder identical to that used in the transmitter whose signals it is attempting to decode. The information bits and parity bits which are detected by the receiver are compared with the information bits and parity bits generated within the receiver. The Hamming distance is computed for each generated information bit. The distance has subtracted from it a magnitude which will cause the difference to be a positive quantity where the information and parity bits correspond and a negative quantity where noise disturbs the received signal. A running sum of these positive and negative quantities is compared with a threshold which increases in stepwise fashion. Where the running sum drops below the threshold, the detection process ceases to go forward and reverses to re-examine previously assumed information bits until a sequence of information bits which results in the running sum once again assuming an increasingly positive value is obtained. Decoded information bits are available as an output where a predetermined bit distance exists between the available bit and the information bit which is then being examined.
As described in such patent, the essence of sequential encoding is the replacement of the "jumping" constraint of block encoding by a "sliding" constraint. In an (n,k) block code, a block of k information bits is caused to provide (n-k) parity bits which depend only on these k information bits. The k information bits and the corresponding (n-k) parity bits are transmitted as a block of n bits and are decoded independently of other similarly obtained blocks of n bits. By contrast, in sequential coding the parity bits are interspersed between successive information bits. The codewords in a convolutional code can be arranged in the form of a tree structure and the encoder selects a path through the tree governed by the information bits.
The sequential decoding operation may be regarded as the process of determining the path in the tree followed by the encoder. As the decoder proceeds to reconstruct a path through a tree based upon a received sequence, it compares the probability of the path that it is currently exploring against a threshold determined by the current noise level that the decoder expects. If the comparison is favorable (the path looks "sufficiently probable"), the decoder continues forward in the tree. If the comparison is unfavorable then either the decoder is on the wrong path because of an atypical noise event that occurred some time previously or the decoder is on the correct path and an atypical noise event is now occurring.
At this point the decoder makes the assumption that the path is incorrect. The decoder reverses itself and searches back in the attempt to find a more probable path. The distance it is allowed to go back in this search depends upon the particular decoding algorithm. For the moment assume that the decoder searches back until it either finds a "sufficiently probable" path or it retreats some fixed number d.sub.0 nodes back without finding a good path. The former case implies that the first path was indeed incorrect as hypothesized and that the new path is more likely correct. The decoder thereupon proceeds forward. The latter case implies that the first path may still be correct and only appears improbable because of atypical noise behavior. The decoder relaxes its criterion of "sufficiently probable" and proceeds as before with a new threshold based upon the current assumption of the noise level.
While sequential decoding of convolutionally encoded data provides an effective error correction scheme for channels with random noise, sequential decoding cannot be used directly on burst noise channels, because bursts of errors cause a sequential decoder to do an enormous amount of searching, which results in the decoder not being able to decode in a reasonable amount of time.
One common method of transforming bursty channels into nonbursty channels is by the process of interleaving. A simple explanation of interleaving is as follows: let N be an integer such that N=p.q. Then a block of N digits x.sub.1,x.sub.2, . . . ,x.sub.N, which is produced by the encoder and is to be transmitted, is input to a p-by-q rectangular array and the array is filled row by row. Once the array is full, the digits are transmitted column by column, so that the order of the digits going over the channel is x.sub.1,x.sub.q+1,x.sub.2q+1,x.sub.(p-1)q+1, x.sub.2,x.sub.q+2, etc. At the receiving end, a similar p-by-q matrix is filled up column by column and then read out row by row so that the original order of the encoder output digits is restored. It is now obvious that a burst in the channel will affect digits x.sub.i,x.sub.i+q,x.sub.i+2q, etc. which are removed from each other by multiples of q positions. Thus, by this method a bursty channel can be made to look like a nonbursty channel.
The usual procedure is to use interleaving and then decode as if the channel were a nonbursty random noise channel. The degree of interleaving, q, is chosen to be much longer than the average length of a burst, so that errors in adjacent digits are now completely uncorrelated.
In U.S. Pat. No. 3,508,197 to Shih Y. Tong, there are disclosed single character error and burst-error correcting systems utilizing convolutional codes to correct any number of bit errors in a single character of I-bit length.
The correction is accomplished at a receiving terminal by generating from a received sequence of characters an error pattern word which identifies the erroneous bits of the character in error and a locator word which identifies which of the received characters contains the erroneous bits. Upon detection of an erroneous character, the error pattern word is added to the erroneous character to obtain the corrected version thereof. The patentee proposes that by interleaving of characters the system can be used for burst-error correction.
In this patent to Tong, an algebraic type of decoding scheme, as opposed to sequential decoding, which is a probabilistic scheme, is employed for error correction. The interleaved burst channel is treated as a random noise channel. Treating an interleaved burst channel as a random noise channel results in a loss of capacity of the channel. It is of course possible to use this interleaving scheme with a sequential decoder as is done in G. D. Forney, Jr. and C. K. Bower, "A High-Speed Sequential Decoder: Prototype Design and Text", IEEE Transactions on Communication Technology, Vol. COM19, No. 5, Oct. 1971, pp.821-835. However, the loss in capacity results in a lower rate of information transmission.
Therefore, it is an object of the present invention to provide a sequential decoder for error correcting on burst noise channels of convolutionally encoded data whereby a minimum loss of capacity results from the interleaving of the burst channel.
It is another object to exploit the higher capacity of burst channels in a probabilistic error correcting decoder utilizing convolutional codes.
It is an object of the invention to provide a method of deriving information from previously decoded data, and using this information in decoding later data.